package com.fwpsl.graph;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author: 风戏fw
 * @date: 2024/4/13
 * @description: 关键路径：从开始点到完成点的最长路径长度叫做关键路径
 */
public class CriticalPath {

    /**
     * 关键路径：首顶点开始，末尾顶点结束。
     *
     * @param graph
     * @param <T>
     * @return
     */
    public static <T> void calcCriticalPath(Graph<T> graph) {
        // 事件最早发生时间
        Map<Vertex<T>, Double> veMap = calcVe(graph);

        // 最早发生时间的最大值
        Double maxVe = veMap.values().stream().max(Double::compareTo).get();

        // 事件最迟发生时间
        Map<Vertex<T>, Double> vlMap = calcVl(graph, maxVe);

        List<Vertex<T>> criticalPath = new ArrayList<>();
        for (Vertex<T> vertex : graph.getVertices()) {
            // 节点的最早发生时间与最迟发生时间相等时，说明该节点在关键路径上
            if (veMap.get(vertex).doubleValue() == vlMap.get(vertex).doubleValue()) {
                criticalPath.add(vertex);
            }
        }

        printCriticalPath(graph, criticalPath);
    }

    /**
     * 事件最早发生时间集合
     *
     * @param graph
     * @param <T>
     * @return
     */
    private static <T> Map<Vertex<T>, Double> calcVe(Graph<T> graph) {
        Map<Vertex<T>, Double> veMap = new HashMap<>();

        // 每个顶点的入度值
        HashMap<Vertex<T>, Integer> inDegreMap = graph.getInDegreMap();

        Queue<Vertex<T>> queue = new LinkedList<>();
        // 从入度为0的顶点开始推算。 初始化最早时间，默认取0
        for (Vertex<T> vertex : graph.getVertices()) {
            veMap.put(vertex, 0d);
            if (inDegreMap.get(vertex) == 0) {
                queue.offer(vertex);
            }
        }

        while (!queue.isEmpty()) {
            Vertex<T> vertex = queue.poll();
            for (Edge<T> edge : vertex.getEdges()) {
                // 取最大值，表示早于这个时间，有前置任务没有完成
                double ve;
                if ((ve = veMap.get(vertex) + edge.getWeight()) > veMap.get(edge.getDestination())) {
                    veMap.put(edge.getDestination(), ve);
                }

                // 更新邻居顶点的入度。当入度归0时，加入队列。
                Integer degree = inDegreMap.get(edge.getDestination()) - 1;
                inDegreMap.put(edge.getDestination(), degree);
                if (degree == 0) {
                    queue.offer(edge.getDestination());
                }
            }
        }

        return veMap;
    }

    /**
     * 事件最迟发生时间
     *
     * @param graph
     * @param maxVe
     * @param <T>
     * @return
     */
    private static <T> Map<Vertex<T>, Double> calcVl(Graph<T> graph, Double maxVe) {
        Map<Vertex<T>, Double> vlMap = new HashMap<>();

        // 每个顶点的出度值
        HashMap<Vertex<T>, Integer> outDegreMap = graph.getOutDegreMap();

        Queue<Vertex<T>> queue = new LinkedList<>();
        // 从出度为0的顶点开始推算。 初始化最迟时间，默认取最早时间的最大值
        for (Vertex<T> vertex : graph.getVertices()) {
            vlMap.put(vertex, maxVe);
            if (outDegreMap.get(vertex) == 0) {
                queue.offer(vertex);
            }
        }

        List<Edge<T>> allEdges = graph.getEdges();
        while (!queue.isEmpty()) {
            Vertex<T> vertex = queue.poll();
            for (Edge<T> edge : vertex.getEdges()) {
                // 取最小值。表示当晚于这个时间，会影响整体进度
                double vl;
                if ((vl = vlMap.get(edge.getDestination()) - edge.getWeight()) < vlMap.get(vertex)) {
                    vlMap.put(vertex, vl);
                }
            }

            // 更新邻居顶点的出度。当出度归0时，加入队列。
            for (Edge<T> edge : getEdgeList(allEdges, vertex)) {
                Integer degree = outDegreMap.get(edge.getSource()) - 1;
                outDegreMap.put(edge.getSource(), degree);
                if (degree == 0) {
                    queue.offer(edge.getSource());
                }
            }
        }

        return vlMap;
    }

    /**
     * 以destination为终点的边的集合
     *
     * @param edges
     * @param destination
     * @param <T>
     * @return
     */
    private static <T> List<Edge<T>> getEdgeList(List<Edge<T>> edges, Vertex<T> destination) {
        return edges.stream().filter(e -> e.getDestination() == destination).collect(Collectors.toList());
    }

    /**
     * 打印关键路径（多条）
     * 通过初始入度为0顶点，推算所有顶点
     *
     * @param graph
     * @param criticalPath
     * @param <T>
     */
    private static <T> void printCriticalPath(Graph<T> graph, List<Vertex<T>> criticalPath) {
        HashMap<Vertex<T>, Integer> inDegreMap = graph.getInDegreMap();
        int pathNum = 0;
        for (Vertex<T> vertex : graph.getVertices()) {
            if (inDegreMap.get(vertex) > 0) {
                continue;
            }

            List<List<Vertex<T>>> pathList = criticalPath(vertex, criticalPath);
            if (pathList == null) {
                continue;
            }

            for (List<Vertex<T>> path : pathList) {
                System.out.print("Critical path（" + (++pathNum) + "）: ");
                System.out.println(Graph.printVerties(path));
            }
        }
    }

    /**
     * 生成有序的关键路径（支持多条关键路径）
     *
     * @param vertex
     * @param criticalPath
     * @param <T>
     * @return
     */
    private static <T> List<List<Vertex<T>>> criticalPath(Vertex<T> vertex, List<Vertex<T>> criticalPath) {
        if (vertex == null || !criticalPath.contains(vertex)) {
            return null;
        }

        // 最后一个事件，直接返回
        List<List<Vertex<T>>> pathList = new ArrayList<>();
        if (vertex.getEdges().size() == 0) {
            List<Vertex<T>> path = new ArrayList<Vertex<T>>() {{
                add(vertex);
            }};
            pathList.add(path);
            return pathList;
        }

        for (Edge<T> edge : vertex.getEdges()) {
            // 先获取子路径
            List<List<Vertex<T>>> subPathList = criticalPath(edge.getDestination(), criticalPath);
            if (subPathList == null) {
                continue;
            }
            for (List<Vertex<T>> subPath : subPathList) {
                List<Vertex<T>> path = new ArrayList<>();
                path.add(vertex);
                path.addAll(subPath);
                pathList.add(path);
            }
        }

        return pathList;
    }

    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addEdge(0, 1, 3);
        graph.addEdge(1, 3, 2);
        graph.addEdge(1, 4, 2);
        graph.addEdge(3, 5, 4);
        graph.addEdge(4, 5, 3);
        graph.addEdge(4, 6, 2);
        graph.addEdge(5, 7, 3);
        graph.addEdge(6, 7, 1);

        // 仅一条关键路径情况
        graph.addEdge(0, 2, 1);
        graph.addEdge(2, 3, 3);
        calcCriticalPath(graph);

        // 多条关键路径情况
//        graph.addEdge(0, 2, 3);
//        graph.addEdge(2, 3, 2);
//        calcCriticalPath(graph);
    }

}
